package com.hans.exercise.sort

/**
 * 归并排序
 * Created by Hans on 2014/4/11.
 */
object MergeSortTest {
  def msSort(nums: List[Int]): List[Int] = {
    def merge(ls: List[Int], rs: List[Int]): List[Int] = {
      (ls, rs) match {
        case (Nil, _) => rs
        case (_, Nil) => ls
        case (l1 :: ls1, r1 :: rs1) =>
          if (l1 < r1) l1 :: merge(ls1, rs)
          else r1 :: merge(ls, rs1)
      }
    }
    val n = nums.length / 2
    if (n == 0) nums
    else {
      val (l, r) = nums splitAt n
      merge(msSort(l), msSort(r))
    }
  }

  def main(args: Array[String]) {
    println(msSort(List(3, 6, 7, 2, 4)))
  }
}
